package by2019;

/**
 * LeetCode 208 实现前缀树，包含插入，查找，查找前缀这三个操作。 搜索引擎会用这种算法实现。
 * 
 * 
 * 分析： 一棵树会有一个根节点，多个子节点（最多26个，因为总共有26个字母）。根节点以String存储，子节点用Trie类型存储。
 * 添加时应该逐级判断，有树存有相同字母则在该树下添加子树。 精确搜索时，搜索到最后一个单词应该判断是否还有子树，如果有子树说明单词不匹配。
 * 
 * 实现：
 * 	以一个TrieNode数组来表示一颗字典树，每个数组会有26个位置，创建子树时创建的是空数组。如果子树下还有子树，则继续填充空的TrieNode数组。
 * ex：
 * 	创建根树root， 此时root为一个空的TrieNode数组。如果添加单词abc，则循环取出'a', 'b', 'c' 判断root的a位置是否为空，可以以 0 - 25 对应字符  'a' - 'z'；
 * 	如果a位置为空则添加一个TrieNode空数组。取出a位置的TrieNode数组，判断b位置是否为空。。。。。以此类推 
 * 
 * @author CARRY ME HOME
 * @date 2019年9月27日 下午4:45:51
 */
public class Trie {
	
	TrieNode root;

	/** Initialize your data structure here. */
	public Trie() {
		root = new TrieNode();
	}
	
	/** 
	 * 遍历字符串的每个字符，判断子树是否添加过该字符，没有则添加该字符到对应位置。遍历完所有字符后添加结束标记。
	 * 
	 * @param word
	 */
	public void insert(String word) {
		
		TrieNode trie = root;
		
		for(int i = 0; i < word.length(); i++) {
			
			char c = word.charAt(i);
			
			if(trie.root[c - 'a'] == null) {
				trie.root[c - 'a'] = new TrieNode();
			}
			
			trie = trie.root[c - 'a'];
		}
		
		trie.end = true;
	}

	/** Returns if the word is in the trie. */
	public boolean search(String word) {
		
		TrieNode trie = root;
		
		for(int i = 0; i < word.length(); i++) {
			
			char c = word.charAt(i);
			
			if(trie.root[c - 'a'] == null)
				return false;
			
			trie = trie.root[c - 'a'];
		}
		return trie.end;
	}

	/**
	 * Returns if there is any word in the trie that starts with the given prefix.
	 */
	public boolean startsWith(String prefix) {
		
		TrieNode trie = root;
		
		for(int i = 0; i < prefix.length(); i++) {
			
			char c = prefix.charAt(i);
			
			if(trie.root[c - 'a'] == null)
				return false;
			
			trie = trie.root[c - 'a'];
		}
		return true;
	}
}

class TrieNode{
	TrieNode[] root;
	boolean end;
	
	TrieNode(){
		root = new TrieNode[26];
		end = false;
	}
}

/**
 * Your Trie object will be instantiated and called as such: 
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word); 
 * boolean param_3 = obj.startsWith(prefix);
 */
